package com.kevin.Code.OfferReviewVersion2;

import java.util.*;

/**
 * @author Vinlee Xiao
 * @Classname WordLadder
 * @Description 剑指 Offer II 108. 单词演变 同Leetcode 127单词接龙 难度 困难
 * @Date 2022/1/13 20:47
 * @Version 1.0
 */
public class WordLadder {

    /**
     * 怎么转换成图的思想来解决问题
     * 转换成图的思想
     * 求两个点之间的距离：通常做法用队列实现广度优先搜索
     *
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        Deque<String> deque1 = new LinkedList<>();
        Deque<String> deque2 = new LinkedList<>();
        HashSet<String> nonVisited = new HashSet<>(wordList);

        //表示从beginWord dao endWord所经历的步数
        int len = 1;
        deque1.addLast(beginWord);

        while (!deque1.isEmpty()) {
            String target = deque1.removeFirst();

            int preSize = deque1.size();

            if (target.equals(endWord)) {
                return len;
            }

            List<String> neighbor = getNeighbor(target);
            for (String s : neighbor) {
                if (nonVisited.contains(s)) {
                    //添加到队列2中
                    deque2.addLast(s);
                    //从没有访问的列表中移除
                    nonVisited.remove(s);
                }
            }
            //为什么判断为空 说明相邻的路径都已经
            if (preSize == 0) {
                len++;
                deque1 = deque2;
                deque2 = new LinkedList<>();
            }

        }


        return 0;
    }

    /**
     * 得到
     *
     * @param beginWord
     * @return
     */
    private List<String> getNeighbor(String beginWord) {

        List<String> result = new ArrayList<>();
        char[] chars = beginWord.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            char oldCharacter = chars[i];

            for (char j = 'a'; j <= 'z'; j++) {
                if (oldCharacter != j) {
                    chars[i] = j;
                    result.add(new String(chars));
                }
            }
            //让接下来改变第二个字母的时候不至于改变多个字母
            chars[i] = oldCharacter;
        }
        return result;
    }
}
